package tu;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v2.edges = List.of(new Edge(v4, 15));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5, 9));
        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);//形成一个图
        dijkstra(graph, v1);
    }
    private static void dijkstra(List<Vertex> graph, Vertex v1) {
        //1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。
        ArrayList<Vertex> list = new ArrayList<>(graph);//加入的graph就相当于上面的那个list.of
        /*2. 为每个顶点分配一个临时距离值
                对于我们的初始顶点，将其设置为零
                对于所有其他顶点，将其设置为无穷大。*/
        v1.dist=0;//初始顶点
        //其它顶点默认值就是无穷大Integer.MAX_VALUE=2^32-1,无穷小Integer.MIN_VALUE=-2^32
        //3.每次选择最小临时距离的未访问顶点，作为新的当前顶点
        //1.最原始写法：但是会引起整数范围溢出，例如Integer.MAX_VALUE-(-1)
        //PriorityQueue<Vertex> pq = new PriorityQueue<>((v2,v3)->v2.dist-v3.dist);
        //2.改进写法：不会出现溢出，是官方写法
        //PriorityQueue<Vertex> pq = new PriorityQueue<>((v2,v3)->Integer.compare(v2.dist, v3.dist));
        //3.最简单写法，最建议，还可以再次直接比较，使用.thenComparingInt(...)
        PriorityQueue<Vertex> pq = new PriorityQueue<>(Comparator.comparingInt(v->v.dist));
        pq.offer(v1);
       /* for (Vertex vertex : graph) {
            pq.offer(vertex);
        }不能直接添加*/
        while (!pq.isEmpty()) {//当集合不为空时，循环继续进行，直到所有内容完成
            Vertex pollCur = pq.poll();//这个就是当前顶点的最小值
            //4. 对于当前顶点，更新邻居的距离，遍历其所有未访问的邻居，并更新它们的临时距离为更小
            updateNeighboursDist(pollCur,pq);
            //5. 当前顶点的邻居处理完成后，把它从未访问集合中删除
            //这个代码实现已经在队列那个poll实现了
        }
        //将最后起始点到任何一点的数值打印出来
        for (Vertex vertex : graph) {
            System.out.println("顶点v1到达"+vertex.name+"的最短路径为"+vertex.dist);

        }
    }
    public static void updateNeighboursDist(Vertex CurNei, PriorityQueue<Vertex> pq) {
        //找到当前顶点的邻居
        for (Edge edge : CurNei.edges) {
            Vertex Nei = edge.linked;//拿到邻居的顶点
                //找到后更新新距离
                /*CurNei.dist之前的顶点到该顶点的值
                 *edge.weight传入的顶点的相邻顶点的权重*/
                int dist= CurNei.dist+ edge.weight;
                //看看更新后的距离和远距离的大小
                //如果更新后的dist和传入的顶点的dist
                if (dist < Nei.dist) {
                    Nei.dist = dist;
                    pq.offer(Nei);
            }
        }
    }
}
